package com.example.Arithmetic.Arithmetic;

import java.util.Arrays;

/**
 * 日期：2024/1/1
 * 时间：10:09
 * 描述：完全背包问题，动态规划，和0/1背包问题很像
 */
public class KnapsackProblemComplete {
    static class Item {
        int index;
        String name;
        int weight;
        int value;

        public Item(int index, String name, int weight, int value) {
            this.index = index;
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Item(" + name + ")";
        }
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(1, "青铜", 2, 3),    // c
                new Item(2, "白银", 3, 4),    // s
                new Item(3, "黄金", 4, 7),    // a
        };
        System.out.println(select(items, 6));
        System.out.println(select1(items, 6));

    }

    /*
            0   1   2   3   4   5   6
        1   0   0   c   c   cc  cc  ccc
        2   0   0   c   s   cc  cs  ccc
        3   0   0   c   s   a   a   ac
     */

    private static int select(Item[] items, int total) {
        int[][] Backpack = new int[items.length][total + 1];
        Item item = items[0];
        for (int i = 0; i < total + 1; i++) {
            if (i >= item.weight) {
                Backpack[0][i] = Backpack[0][i - item.weight] + item.value;
            }
        }
        for (int i = 1; i < items.length; i++) {
            item = items[i];
            for (int j = 0; j < total + 1; j++) {
//                装得下
                if (j >= item.weight) {
                    Backpack[i][j] = Math.max(Backpack[i - 1][j], Backpack[i][j - item.weight] + item.value);
                } else {
//                    装不下，拿上一列填值
                    Backpack[i][j] = Backpack[i - 1][j];
                }
            }
        }
        System.out.println(Arrays.deepToString(Backpack));
        return Backpack[items.length - 1][total];
    }

    //    完全背包降维处理，一维数组
    private static int select1(Item[] items, int total) {
        int[] Backpack = new int[total + 1];
        for (int i = 0; i < items.length; i++) {
            Item item = items[i];
            for (int j = 0; j <= total; j++) {
                if (j >= item.weight) {
                    Backpack[j] = Math.max(Backpack[j], Backpack[j - item.weight] + item.value);
                }
            }
        }
        return Backpack[total];
    }
}